package com.leetcode.LC_MED;

import java.util.LinkedList;
import java.util.Queue;

public class LC200 {
    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rs = 0;
        int row = grid.length;
        int col = grid[0].length;

        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    queue.add(new int[]{i, j});
                    rs++;
                    grid[i][j] = '0';
                    while (queue.size() > 0) {
                        int[] poll = queue.poll();
                        int x = poll[0];
                        int y = poll[1];
                        if (y + 1 < col && grid[x][y + 1] == '1') {//上
                            grid[x][y + 1] = '0';
                            queue.add(new int[]{x, y + 1});
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {//下
                            grid[x][y - 1] = '0';
                            queue.add(new int[]{x, y - 1});
                        }
                        if (x + 1 < row && grid[x + 1][y] == '1') {//左
                            grid[x + 1][y] = '0';
                            queue.add(new int[]{x + 1, y});
                        }
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {//右
                            grid[x - 1][y] = '0';
                            queue.add(new int[]{x - 1, y});
                        }
                    }

                }
            }
        }
        return rs;
    }
}
